package first.niuke.midding;



import java.util.ArrayList;
import java.util.Arrays;

/**
 * @ClassName NC46
 * @description:
 * @author: 荣燊
 * @create: 2021-06-28 16:09
 **/
public class NC46 {

    public static void main(String[] args) {
        int[] ints1 = {100,10,20,70,60,10,50};
        int target1 = 80;

        int[] ints2 = {2,3,6,7};
        int target2 = 7;
        ArrayList<ArrayList<Integer>> arrayLists = combinationSum3(ints2, target2);
        System.out.println(arrayLists);
    }


    // 加起来和为目标值的组合

    /**
     * 给出一组候选数C 和一个目标数T，找出候选数中起来和等于T 的所有组合。
     * C 中的每个数字在一个组合中只能使用一次。
     * 注意：
     * 题目中所有的数字（包括目标数T ）都是正整数
     * 结果中不能包含重复的组合,组合中的数字要按照递增排序
     * 组合之间的排序按照索引从小到大依次比较，小的排在前面，如果索引相同的情况下数值相同，则比较下一个索引。
     */
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        // 先将数组排序
        if (num == null || num.length == 0) {
            return null;
        }
        Arrays.sort(num);
        return null;
    }

    public void dfs(int[] num, int target, ArrayList<Integer> tmp) {
        if (target == 0) {
            result.add(tmp);
            return;
        }

    }


    // leetcode39,给定一个无重复元素的数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
    // candidates中的数字可以无限制重复被选取。https://leetcode-cn.com/problems/combination-sum/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/
    static ArrayList<ArrayList<Integer>> result2 = new ArrayList<>();
    public static ArrayList<ArrayList<Integer>> combinationSum3(int[] num, int target) {
        // 先将数组排序
        if (num == null || num.length == 0) {
            return null;
        }
        ArrayList<Integer> tmp = new ArrayList<>();
        dfs1(num, 0, target, tmp);
        return result2;
    }

    public static void dfs1(int[] num, int begin, int target, ArrayList<Integer> tmp) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            result2.add(new ArrayList<>(tmp));
            return;
        }
        // 从begin开始，剪枝操作，注意看解析中的树
        for (int i=begin; i<num.length; i++) {
            tmp.add(num[i]);
            dfs1(num, i, target-num[i], tmp);
            tmp.remove(tmp.size()-1);
        }
    }
    //友情提示：如果题目要求，结果集不计算顺序，此时需要按顺序搜索，才能做到不重不漏。
    //力扣」第 47 题（ 全排列 II ）、「力扣」第 15 题（ 三数之和 ）也使用了类似的思想，使得结果集没有重复。
    /**leetcode40:
     * 给定一个数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
     *   candidates中的每个数字在每个组合中只能使用一次。
     * 说明：
     *   所有数字（包括目标数）都是正整数。
     *   解集不能包含重复的组合。
     */


}
